As computer technology has advanced, so too has the need for security within computers. One popular type of security incorporated into computers, typically through the operating system, is user-based restrictions on the various objects in the computer (e.g., hardware resources, software components, etc.). Each user of a computer system has one or more corresponding identifiers, and each object has one or more rules that define access rights (e.g., which users can access the object and how they can access it).
FIG. 1 illustrates an example of a current access control system. Each object in the computer system has a corresponding access control list (ACL) 100 that is made up of multiple (m) access control elements (ACEs) 102 that each include a security identifier (SID) 104. Additionally, each user has a list of multiple (n) SIDs 106. When the user desires to access the object, the SIDs 106 are compared to the SIDs 104 to determine whether any of the SIDs 106 match any of the SIDs 104. If a match exists then the user can access the object (subject to any other access limitations identified in the ACE). However, if no match exists then the user cannot access the object.
However, in the system illustrated in FIG. 1, to compare the SIDs 106 with the SIDs 104, a linear search through all m SIDs 104 for each of the n SIDs 106 may be needed, requiring a large number of operations (that is, m×n operations). Such a large number of operations can adversely affect the performance of the computer system. This performance drain is only exacerbated by the fact that such comparisons are typically required each time a new object is accessed (which can be quite frequently). Thus, it would be beneficial to provide an improved way to perform such comparisons.
One solution to reduce the number of such comparisons would be to use hashing to determine which comparisons to make. To use hashing, a hash key would be generated from each of the SIDs in the ACL. This hash key would then be used as an index into a hash table to identify a value from the hash table that indicates, based on the hash key, which SIDs corresponding to the user are likely matches. One problem with this solution, however, is the memory storage requirements. The hash table would require 2b locations, where b represents the number of bits in the hash key. The memory storage requirements can thus grow quite large, especially as the size of the hash key increases and the amount of data stored in each location of the hash table increases. Large memory storage requirements can reduce the performance of the comparison process (counteracting the benefits of hashing) due to memory page faults in systems employing virtual memory.
The invention described below addresses these disadvantages, providing an improved hashing structure using multiple sub-hashes.